---
title: "连号区间数"
created: 2025-11-28
tags:
  - 算法
---

# 连号区间数

## 题目 [连号区间数](https://www.acwing.com/problem/content/1212/)

![[image-180fcf1d.png]]

## 思路分析

![[image-9a7a3794.png]]

![[image-ce9bfc8b.png]]

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10010;

int a[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    int cnt=0;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            int maxv=-0x3f3f3f,minv=0x3f3f3f;

            for(int k=i;k<=j;k++){

                maxv=max(maxv,a[k]);

                minv=min(minv,a[k]);

            }

            if(maxv-minv==j-i)

                cnt++;

        }

    }

    cout<<cnt;

    return 0;

}
```

其实大概也猜到了 三重循环 n=10000 应该还是会tle

![[image-db248a43.png]]
![[image-781bbcb8.png]]

再模拟一遍发现 k完全不需要 j在往后走时 直接确定了区间长度 区间长度确定了 只需要判断最大值与最小值的差值即可

两重循环 $n^2$ 且j不走回头路 大概是2n 绰绰有余

![[image-f8d9c79a.png]]

这样来看 oi赛制还是有点难的 只能交一次 你不能根据报错来反思调整代码

不要抱着试一试的心态 大概估计出来了写法 再想想时间复杂度 还能怎么优化

实在想不出来 就算了呗 反正有一半的分

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10010;

int a[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    int cnt=0;

    for(int i=1;i<=n;i++){

        int maxv=-0x3f3f3f,minv=0x3f3f3f;

        for(int j=i;j<=n;j++){

            maxv=max(maxv,a[j]);

            minv=min(minv,a[j]);

            if(maxv-minv==j-i)

                cnt++;

        }

    }

    cout<<cnt;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[蹄子剪刀布|蹄子剪刀布]] 🏠 [[00-刷题理模型]] ➡️ [[逆行|逆行]]